package leetcode.hot100;

/**
 * leetcode-hot100:除自身以外数组的乘积
 * 测试链接: https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-100-liked
 *
 * 前后缀分解
 *
 */
public class ProductOfArrayExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        // 先计算后缀积
        ans[n - 1] = 1;
        for(int i = n - 2; i >= 0; i--){
            ans[i] = ans[i + 1] * nums[i + 1];
        }
        // 优化空间，一边计算pre，一边把pre直接乘到后缀积上
        int pre = 1;
        for(int i = 0; i < n; i++){
            // 此时pre为 nums[0] 到 nums[i - 1]的乘积
            ans[i] *= pre;
            pre *= nums[i];
        }
        return ans;
    }
}
